package sun.scheduler.util.collections;

import java.util.Arrays;
import java.util.Comparator;

/**
 * Represents a heap that allows for heap data to be in- or decreased. You may either replace some
 * data with a in-/decreased value or notify this heap that some data has been decreased. For
 * performance reasons you have to keep track of the index at whith the data was inserted
 * externally. This can be done with a {
 *
 * @see HashMap} as follows {@code heap.add(someData); map.put(someData, heap.size());}
 *
 * @author mfj
 * @param <E> the genric data content
 */
public class ModifiableHeap<E> extends Heap<E>
{
    // matches the id of the data with 
    // indexes of the queue elements
    private int[] posIdMap;

    private int[] idPosMap;


    public ModifiableHeap(E[] array,
            Comparator<E> comparator)
    {
        super(array, comparator);
        idPosMap = new int[queue.length];
        posIdMap = new int[queue.length];
    }


    public ModifiableHeap(Comparator<E> comparator)
    {
        super(comparator);
        idPosMap = new int[queue.length];
        posIdMap = new int[queue.length];
    }


    public ModifiableHeap(int initialCapacity,
            Comparator<E> comparator)
    {
        super(comparator);
        idPosMap = new int[queue.length];
        posIdMap = new int[queue.length];
    }


    @Override
    protected void increaseCapacity()
    {
        super.increaseCapacity();
        idPosMap = Arrays.copyOf(idPosMap, queue.length);
        posIdMap = Arrays.copyOf(posIdMap, queue.length);
    }


    @Override
    public void add(E data)
    {
        if ( size >= posIdMap.length )
            increaseCapacity();

        posIdMap[size] = idPosMap[size] = size;
        super.add(data);
    }


    @Override
    protected int swapData(int i, int j)
    {
        int firstId = posIdMap[i];
        int secondId = posIdMap[j];

        idPosMap[firstId] = j;
        idPosMap[secondId] = i;

        posIdMap[i] = secondId;
        posIdMap[j] = firstId;

        return super.swapData(i, j);
    }


    /**
     * Restores the heap property after the key of some element was decreased. The queue uses the
     * index at which the decreased element was inserted as identifyer. I.e. suppose {@code this.size() == 3}
     * then then the id after
     * {@code add(data)} would be 3. You may use HashMaps or arrays to keep track of the id's.
     *
     * @param index the index at which the element was added to this queue.
     * @return the decreased key.
     */
    public E decreaseKey(int index)
    {
        int pos = idPosMap[index];
        E decreased = queue[pos];
        heapifyUp(pos, decreased);
        return decreased;
    }


    /**
     * Restores the heap property after the key of some element was increased. The queue uses the
     * index at which the decreased element was inserted as identifyer. I.e. suppose {@code this.size() == 3}
     * then then the id after
     * {@code add(data)} would be 3. You may use HashMaps or arrays to keep track of the id's.
     *
     * @param index the index at which the element was added to this queue.
     * @return the increased key.
     */
    public E increaseKey(int index)
    {
        int pos = idPosMap[index];
        E increased = queue[pos];
        heapifyDown(pos, increased);
        return increased;
    }


    /**
     * Changes some data within this heap with a decreased data value.
     *
     * @param index index the index at which the element was added to this queue.
     * @param data the decreased data value
     * @return the decreased key.
     * @throws IllegalArgumentException if the data is larger then the original data
     */
    public E decreaseKey(int index, E data)
    {
        int pos = idPosMap[index];
        if ( comparator.compare(data, queue[pos]) > 0 )
            throw new IllegalArgumentException();

        heapifyUp(pos, data);
        return data;
    }


    /**
     * Changes some data within this heap with a increased data value.
     *
     * @param index index the index at which the element was added to this queue.
     * @param data the decreased data value
     * @return the increased key.
     * @throws IllegalArgumentException if the data is smaller then the original data
     */
    public E increaseKey(int index, E data)
    {
        int pos = idPosMap[index];
        if ( comparator.compare(data, queue[pos]) < 0 )
            throw new IllegalArgumentException();

        heapifyDown(pos, data);
        return data;
    }
    
    /**
     * Changes the key of a specific element within this heap.
     * @param index index the index at which the element was added to this queue.
     * @param data the new data value
     * @return the new data value.
     */
    public E changeKey(int index, E data)
    {
        int pos = idPosMap[index];
        E oldData = queue[pos];
        if ( comparator.compare(data, oldData) > 0 )
            heapifyDown(pos, data);
        else 
            heapifyUp(pos, data);
            
        return data;
    }
}